package hot100;

import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class Solution264 {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.offer(1L);
        Set<Long> set = new HashSet<>();
        set.add(1L);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = queue.poll();
            set.remove(ans);
            if (!set.contains(2 * ans)) {
                queue.offer(2 * ans);
                set.add(2 * ans);
            }
            if (!set.contains(3 * ans)) {
                queue.offer(3 * ans);
                set.add(3 * ans);
            }
            if (!set.contains(5 * ans)) {
                queue.offer(5 * ans);
                set.add(5 * ans);
            }
        }
        return (int) ans;
    }

    public static void main(String[] args) {
        Solution264 solution264 = new Solution264();
        System.out.println(solution264.nthUglyNumber(1407));
    }
}
